package arithmetic.LeetCode;

import java.util.Arrays;

import org.junit.jupiter.api.Test;

/**
 * https://leetcode.cn/problems/maximum-score-from-removing-stones/
 * @author jiangfeng on 2022/12/21
 */
public class RemovingStones1754 {

    @Test
    public void test(){
        //System.out.println(maximumScore(2,4,6));
        //System.out.println(maximumScore(24, 19, 24));
        // 5 + (19,19,19) 18,18,19
        // 5+1+ 9+18.  算法.
        System.out.println(maximumScore(1019, 375, 664));
        System.out.println(i);
    }

    public int maximumScore(int a, int b, int c) {
        // 思路1,贪心算法,每次先排序,减最大的两个必然是最优解

        int[] arr = new int[]{a,b,c};
        Arrays.sort(arr);
        int result=0;
        while(!(arr[0]==0 && arr[1]==0)){
            arr[2]--;
            arr[1]--;
            result++;
            Arrays.sort(arr);
        }

        return result;

    }

    public int maximumScore2(int a, int b, int c) {
        // 思路2, 数学解法:如果c>=a+b 则结果为a+b. 如果c<a+b,则结果为(a+b+c)/2
        int[] arr = new int[]{a,b,c};
        Arrays.sort(arr);
        return (arr[2]>=arr[1]+arr[0])?arr[1]+arr[0]:((a+b+c)/2);

    }



    public int maximumScore3(int a, int b, int c) {
        // 递归
        // dp(n) = d(n-1)+1.
        int[][][] arr = new int[a+1][b+1][c+1];
        if(check(a,b,c)){
            return 0;
        }
        int na = maximumScore_(a, b - 1, c - 1, arr);
        int nb = maximumScore_(a - 1, b, c - 1, arr);
        int nc = maximumScore_(a - 1, b - 1, c, arr);
        return Math.max(Math.max(na, nb), nc) + 1;
    }


    public int maximumScore1(int a, int b, int c) {
        // 递归
        // dp(n) = d(n-1)+1.
        // int[][][] arr = new int[a][b][c];
        if(check(a,b,c)){
            return 0;
        }
        int na = maximumScore1(a,b-1,c-1);
        int nb = maximumScore1(a-1,b,c-1);
        int nc = maximumScore1(a-1,b-1,c);
        return Math.max(Math.max(na,nb),nc)+1;
    }

    public static int i =0;

    public int maximumScore_(int a, int b, int c, int[][][] arr) {
        // System.out.println(a + "," + b + "," + c);
        if (check(a, b, c)) {
            return 0;
        }
        int v = arr[a][b][c];
        if (v > 0) {
            return v;
        }
        i++;
        int na = maximumScore_(a, b - 1, c - 1, arr);
        int nb = maximumScore_(a - 1, b, c - 1, arr);
        int nc = maximumScore_(a - 1, b - 1, c, arr);
        arr[a][b][c] = Math.max(Math.max(na, nb), nc) + 1;
        return arr[a][b][c];
    }


    public boolean check(int a, int b, int c) {
        if (a < 0 || b < 0 || c < 0) {
            return true;
        }
        return (a == 0 && b == 0) || (a == 0 && c == 0) || (c == 0 && b == 0);
    }
}
